from RandomList import GetRandomList
import sys

# 算法导论里的精简写法, 原地修改
def quick_sort( arr, l, r):
    if l < r:
        q = partition( arr, l, r)
        quick_sort( arr, l, q - 1)
        quick_sort( arr, q + 1, r)

def partition( arr, l, r):
    x = arr[r]
    i = l - 1
    for j in range(l, r):
        if  arr[j] <= x:
            i += 1
            arr[i],  arr[j] =  arr[j],  arr[i]
    arr[i + 1],  arr[r] =  arr[r],  arr[i + 1]
    return i + 1

if __name__ == "__main__":
    sys.setrecursionlimit(10000)
    Arr = GetRandomList(5000)
    quick_sort(Arr, 0, len(Arr) - 1)